Aims: The TeV BL Lac object Markarian 501 is a complex, core dominated radio source, with a one sided, twisting jet on parsec scales. In the present work, we attempt to extend our understanding of the source physics to regions of the radio jet which have not been accessed before. Methods: We present new observations of Mrk 501 at 1.4 and 86 GHz. The 1.4 GHz data were obtained using the Very Large Array (VLA) and High Sensitivity Array (HSA) in November 2004, in full polarization, with a final r.m.s. noise of 25 microJy/beam in the HSA total intensity image; the 86 GHz observations were performed in October 2005 with the Global Millimeter VLBI Array (GMVA), providing an angular resolution as good as 110 x 40 microarcseconds. Results: The sensitivity and resolution provided by the HSA make it possible to detect the jet up to ~700 milliarcseconds (corresponding to a projected linear size of ~500 pc) from its base, while the superior resolution of the 86 GHz GMVA observations probes the innermost regions of the jet down to ~200 Schwarzschild radii. The brightness temperature at the jet base is in excess of 6e10 K. We find evidence of limb brightening on physical scales from <1 pc to ~40 pc. Polarization images and fits to the trend of jet width and brightness vs. distance from the core reveal a magnetic field parallel to the jet axis.